class Solution {
    int[] tmp;//设置全局变量，避免大量递归带来的时空效率的拉低
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int s, int e) {
        if(s >= e) return;
        //根据中间节点划分区间
        int mid = (s + e) / 2;
        //把左右区间排序
        mergeSort(nums, s, mid);
        mergeSort(nums, mid + 1, e);
        //合并两个有序数组
        merge(nums, s, mid, e);
    }
    public void merge(int[] nums, int s, int mid, int e) {
        int s1 = s, e1 = mid, s2 = mid + 1, e2 = e;
        
        int k = 0;
        while(s1 <= e1 && s2 <= e2) tmp[k++] = nums[s1] <= nums[s2] ? nums[s1++] : nums[s2++];
        //处理没有遍历完的数组
        while(s1 <= e1) tmp[k++] = nums[s1++];
        while(s2 <= e2) tmp[k++] = nums[s2++];
        for(int i = s; i <= e; i++) nums[i] = tmp[i - s]; 
    }
}